The statements in this section merely provide background information related to the present disclosure and may not constitute prior art.
Underlying the success of low-density parity-check (LDPC) codes and its acceptance into emerging digital video broadcasting (DVB-S2) and wireless standards (802.11, 802.12, 802.20) has been its fast and hardware realizable decoding process. Conventional LDPC decoders are either based on sum-product processes or use suboptimal min-sum (MS) processes. Both decoding processes are soft-decision processes that operate in either probability or log-likelihood ratio (LLR) domains and are amenable to parallel analog and digital hardware implementations. In particular, analog decoders are attractive over their digital counterparts because of their potential to achieve superior energy efficiency at fixed decoding speeds. Popular topology for analog LDPC decoders has been based on trans-linear circuits using either bipolar transistors or MOS transistors biased in weak inversion. Alternate analog topology based on min-sum approximation of sum-product process has been reported and has been mapped onto optical networks for high-speed decoding.
The LDPC decoding process can be expressed by equations in terms of a log-MAP formulation. LDPC codes are a class of binary linear block codes whose parity check matrix contains only a few 1's in comparison to the amount of 0s. An example of a parity check matrix H and its tanner or factor graph are shown in FIG. 1. A factor graph consists of variable nodes vk,k=1, . . . ,Nc which are connected to check nodes ci,i=1 . . . ,M using edges. The number of edges associated with each node (also known as degree of the node) is represented by dc for check nodes and as dv for variable nodes. The parity check matrix for LDPC code is represented by H(dv,dc).
For detailed treatment and analysis of LDPC decoding based on sum-product process, reference may be had to J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of block and convolutional codes,” IEEE Trans. Inf. Theory, vol. IT-42, no. 3, pp. 429445, March 1996, which is incorporated herein by reference in its entirety for any purpose. More briefly, let Vi denote a set of check nodes connected to the variable node vi and Vi˜j represent the set of check nodes other than cj that are connected to variable node vi. Similarly let Cj denote a set of variable nodes connected to the check node cj and Cj˜i represent the set of variable nodes other than the node vi connected to cj.
In a message passing process, each check node cj receives messages from its set of neighbors Cj (denoted by L(vi→cj)) and computes messages to be sent to the variable nodes viεCj (denoted by L(cj→vi)) according to
                                          L            ⁡                          (                                                c                  j                                →                                  v                  i                                            )                                =                      2            ⁢                                          tanh                                  -                  1                                            ⁡                              [                                                      ∏                                                                  v                        k                                            ∈                                              C                                                  j                          ~                          1                                                                                                      ⁢                                      tanh                    ⁡                                          (                                                                        L                          (                                                                                    v                              k                                                        →                                                          c                              j                                                                                                      2                                            )                                                                      ]                                                    ⁢                                                      (        1        )            where tan h(χ)=(exp(χ)−exp(−χ))/(exp(χ)+exp(−χ)). In subsequent iterations, the variable nodes vi receive messages from its check nodes cjεVi and re-computes messages (denoted by L(vi→cj)) that will be sent to the check node cj according to
                              L          ⁡                      (                                          c                j                            →                              v                i                                      )                          =                              L            ⁡                          (                              v                i                            )                                +                                    ∑                                                c                  k                                ∈                                  V                                      j                    ~                    1                                                                        ⁢                                          L                ⁡                                  (                                                            c                      k                                        →                                          v                      i                                                        )                                            .                                                          (        2        )            Messages are propagated back and forth between the variable and check nodes for a pre-determined number of iterations before a decision on the received bits is performed.
In LDPC decoding, the computationally intensive core is equation (1) which requires evaluations of hyperbolic function. Several approximations have been proposed in literature that approximate floating point computation of hyperbolic functions, some of which include the use of finite resolution look tables for digital implementations or a min-sum approximation for analog implementations. Equation (1) can be computed recursively according to the following process:                1) Initialize L(vi→cj)=−∞.        2) Repeat the following recursion for each element vjεCj˜i         
                              L          ⁡                      (                                          v                i                            →                              c                j                                      )                          ←                              log            ⁡                          [                                                1                  +                                      ⅇ                                                                  L                        ⁡                                                  (                                                                                    v                              i                                                        →                                                          c                              j                                                                                )                                                                    +                                              L                        ⁡                                                  (                                                                                    c                              j                                                        →                                                          v                              i                                                                                )                                                                                                                                                          ⅇ                                          L                      ⁡                                              (                                                                              v                            i                                                    →                                                      c                            j                                                                          )                                                                              +                                      ⅇ                                          L                      ⁡                                              (                                                                              c                            j                                                    →                                                      v                            i                                                                          )                                                                                                        ]                                .                                    (        3        )            
The update equation (3) is the fundamental operation for implementing LLR based LDPC decoders. For the sake of brevity, the operation (3) can be compactly represented as x←log(1+eχ+y)−log(ex+ey) where the arbitrary variables x, y represent the likelihoods. Before we introduce the log-MAP formulation and subsequently margin propagation, we will first decompose variables x and y into differential representations as x=x+−x− and y=y+−y− with x+,x−,y+,y−≧0. Such a decomposition is desirable for analog circuit implementation because a fully differential architecture is robust to common-mode interference. Equation (3) can be represented as the following differential updates:x+←log└ex++y++ex−+y−┘  (4)x−←log└ex++y−+ex−+y+┘  (5)Each of the updates (4), (5) are in the form of a “log-MAP” normalization which are popular in Bayesian network literature.